import copy

grammar5 = {
    "terminals": {"a", "b", "c", "d","e","#"},  # #表示结束
    "non_terminals": {"S'", "S", "A"},
    "start": "S'",
    "productions": [
        ("S'", ["S"]),  # (0) S' :== S
        ("S", ["a","A", "d"]), # (1) S :== aAd   
        ("S", ["b", "A", "c"]),  # (2) S :== aba
        ("S", ["a", "e", "c"]),  # (4) S :== aec
        ("S", ["b", "e", "d"]),  # (4) S :== bed
        ("A", ["e"]),  # (5) A :== E
    ],
}
print(grammar5)
AnalyzerTable = {
    # 状态0
    '0': {'a': 'S2',
          'b': 'S3',
          'c': '',
          'd': '',
          'e': '',
          '#': '',
          'S': 'g1',
          'A': '',
          },
    # 状态1
    '1': {'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': '',
          '#': 'acc',
          'S': '',
          'A': '',
          },
    # 状态2
    '2': {'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': 'S5',
          '#': '',
          'S': '',
          'A': 'g4',
          },
    # 状态3
    '3':  {'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': 'S7',
          '#': '',
          'S': '',
          'A': 'g6',
          },
    # 状态4
    '4':{'a': '',
          'b': '',
          'c': '',
          'd': 'S8',
          'e': '',
          '#': '',
          'S': '',
          'A': '',
          },
    # 状态5
    '5': {'a': '',
          'b': '',
          'c': 'S9',
          'd': 'r5',
          'e': '',
          '#': '',
          'S': '',
          'A': '',
          },
    # 状态6
    '6':  {'a': '',
          'b': '',
          'c': 'S10',
          'd': '',
          'e': '',
          '#': '',
          'S': '',
          'A': '',
          },
    # 状态7
    '7': {'a': '',
          'b': '',
          'c': 'r5',
          'd': 'S11',
          'e': '',
          '#': '',
          'S': '',
          'A': '',
          },
    # 状态8
    '8': {'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': '',
          '#': 'r1',
          'S': '',
          'A': '',
          },
    # 状态9
    '9':{'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': '',
          '#': 'r3',
          'S': '',
          'A': '',
          },
    # 状态10
    '10':{'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': '',
          '#': 'r2',
          'S': '',
          'A': '',
          },
    # 状态11
    '11':{'a': '',
          'b': '',
          'c': '',
          'd': '',
          'e': '',
          '#': 'r4',
          'S': '',
          'A': '',
          },
}
print(AnalyzerTable)

# LR0语法分析器


def SLR1Analyzer(Grammar, InputStr):
    """
    使用LR(0)分析器分析给定的文法和输入字符串。
    
    Args:
        Grammar (dict): 文法字典，包含非终结符、终结符、产生式等信息。
        InputStr (str): 输入字符串。
    
    Returns:
        bool: 分析结果，True表示接受，False表示拒绝。
    """
    StackState = ['0']  # 状态栈初始状态为0
    StackInput = []  # #输入栈
    print(f"(状态栈：{StackState[-1]},输入符号栈：'')")
    length = len(InputStr)
    i = 0
    while i<=length-1:
        Chr = InputStr[i]  # 获取当前输入字符
        print(f"当前输入：{Chr}")
        TopState = StackState[-1]  # 获取栈顶状态
        Action = AnalyzerTable[TopState][Chr]
        if Action == '':  # 如果没有动作，则报错
            print("Error: No such action")
            return False
        elif Action[0] == 'a':  # 接受动作
            if i == length - 1:  # 如果已经到达输入字符串的末尾，则接受
                print("Accepted")
                return True
        elif Action[0] == 'S':  # 状态转移动作
            StackState.append(Action[1:])  # 转移状态
            StackInput.append(Chr)  # 将输入字符压入输入栈
            i = i + 1 # 只有在当前字符入栈后，才读入下一个字符
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
        elif Action[0] == 'r':  # 规约动作
            Production = Grammar["productions"][int(Action[1:])]
            ProdLeft = Production[0]  # 获取产生式左部
            ProdRight = Production[1]  # 获取产生式右部
            if ProdRight[0] != 'ε': # 如果产生式右部不为空，则弹出对应的输入字符
                for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                    StackState.pop()
                    StackInput.pop()
                # 栈发生变化后，打印当前状态和输入字符
                print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
            StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
            # 栈发生变化后，打印当前状态和输入字符
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")

            # 循环处理状态栈顶的动作，直到没有动作为止
            Action = ''
            TopSymbol = StackInput[-1] if len(StackInput) > 0 else ''
            if TopSymbol != '': # 如果栈不为空，则继续处理               
                TopState = StackState[-1] # 状态发生变化，获取当前状态
                Action = AnalyzerTable[TopState][TopSymbol]  # 可能会涉及新的归约或状态转移
                while (Action != '') and ((Action[0] == 'r') or (Action[0] == 'g')):
                    if Action[0] == 'r':  # 规约动作
                        Production = Grammar["productions"][int(Action[1:])]
                        ProdLeft = Production[0]  # 获取产生式左部
                        ProdRight = Production[1]  # 获取产生式右部
                        for j in range(len(ProdRight)):  # 弹出len(ProdRight)个状态和字符
                            StackState.pop()
                            StackInput.pop()
                            # 栈发生变化后，打印当前状态和输入字符
                            print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                        StackInput.append(ProdLeft)  # 将产生式左部压入输入栈
                    elif Action[0] == 'g':  # 状态转移动作
                        StackState.append(Action[1:])  # 转移状态
                        # 栈发生变化后，打印当前状态和输入字符
                        print(f"(状态栈：{StackState},输入符号栈：{StackInput})")
                    TopSymbol = StackInput[-1] if len(StackInput) > 0 else ''
                    Action = ''
                    if TopSymbol != '': # 如果栈不为空，则继续处理   
                        TopState = StackState[-1] # 状态发生变化，获取当前状态
                        Action = AnalyzerTable[TopState][TopSymbol]  # 重新获取当前状态下的动作
                #endwhile

    #endfor
    return False


print("Analyzer Testing 1 --------------------------------")
InputString = "aeb#"
Rst = SLR1Analyzer(grammar5, InputString)
print(f"The syntax of {InputString} is {Rst}")

print("Analyzer Testing 2 --------------------------------")
InputString = "aed#"
Rst = SLR1Analyzer(grammar5, InputString)
print(f"The syntax of {InputString} is {Rst}")
